All Questions
Tagged with ds.algorithmscc.complexity-theory
260 questions
0votes
0answers
56views
Heuristic for Solving 3-SAT Based on Literal Sign Analysis and a Correction Phase
I am trying a heuristic approach for solving 3-SAT instances without backtracking. The method relies on an initial variable assignment based on literal signs, followed by a targeted correction phase ...
1vote
0answers
70views
Are there any natuarlly occurring problem having an algorithm with run time O(n^d) with d > 10? [duplicate]
Are there any naturally occurring polynomial time solvable problem with degree of the polynomial greater than 10 ? The closest I found is AKS's Primality algorithm with runtime $\tilde{O}(n^{12})$ but ...
- 111
0votes
0answers
106views
$\mathsf{GCD}(a,b)\not\in TC^0$ while fixed dimension feasibility $ILP$ is in $TC^0$ consistent with our knowledge?
The reduction from $\mathsf{GCD}(a,b)$ is to do binary search on the feasibility of program $$r_1<au+bv<r_2$$ $$u,v\in\mathbb Z$$ where $a,b$ are given integers and we do binary search with ...
- 13.5k
2votes
0answers
73views
Terminology for computation vs. output
Is there a widely accepted name and/or notation for the computational process of an algorithm as opposed to its output? To clarify, suppose I have an algorithm $A$, and I denote as $A(x)$ the output ...
2votes
0answers
75views
Complexity of single bit recovery version of Integer Factorization problem
Consider the integer factoring problem with exactly 2 prime factors $p.q=N$. Given $N$ find the prime factors $p$ and $q$. The problem is notoriously difficult (on classical computers) and is the ...
- 851
4votes
2answers
171views
Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?
It is known that many-tape Turing machines can be simulated by a one tape Turing machine with extra runtime costs. Furthermore, a single-tape Turing machine with a larger alphabet can be simulated by ...
1vote
0answers
142views
Efficient algorithm to construct simple polygon from non-crossing orthogonal line segments
Given a set of $N$ non-crossing orthogonal (vertical and horizontal) line segments on the plane, is there an efficient algorithm to construct a simple orthogonal polygon that passes through all given ...
0votes
0answers
87views
Evidence extended GCD is in $TC^0$
Despite centuries of search extended $GCD$ is known to accommodate one algorithm which is the Euclidean algorithm (the solution through Integer Linear Programming which needs basis reduction goes ...
- 13.5k
4votes
1answer
92views
Reference request: finite field computation over the Word-RAM model
Let $q = p^\ell$ be a positive integer power of a prime $p$, of size $q = \text{poly}(n)$. Over the Word-RAM model (with words of size $O(\log n)$), how quickly can we perform addition and ...
- 696
4votes
0answers
95views
Uniform lower bounds in terms of the matrix multiplication exponent $\omega$?
Let $f(n)$ denote the minimum number of arithmetic operations needed for multiplying two $n\times n$ matrices, and $\omega = \inf\{p \ge 0: f(n) = O(n^p)\}$ be the matrix multiplication exponent. Is ...
0votes
1answer
345views
Complexity of simplex method
What is the complexity of the simplex method in terms of Big O in the general case? I saw two variants: O(2^n) and O(2^(n+m)), where n is the number of variables and m is the number of constraints
6votes
1answer
393views
Condition Number dependent algorithms for matrix operations
Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where $\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{...
- 958
1vote
1answer
107views
Exchange cards with sum requirement
Given are positive integers $a_1,\dots,a_{2k},b_1,\dots,b_{2k},S$ such that $\sum_{i=1}^ka_i = \sum_{i=k+1}^{2k}a_i = S$ and $\sum_{i=1}^kb_i = \sum_{i=k+1}^{2k}b_i = S$. There are $2k$ cards, card $i$...
- 133
14votes
1answer
2kviews
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in ...
1vote
0answers
104views
On the borderline between natural and artificial problems
While there is no formal definition of what constitutes a natural algorithmic problem, in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
- 11.6k
